#ifndef GRAPH_H
#define GRAPH_H

#include <vector>
#include <unordered_set>
#include <array>
#include <stack>
using std::vector;
template <typename T>
using USet = std::unordered_set<T>;
using std::array;
using std::stack;


typedef enum {GVWHITE, GVGREY, GVBLACK}GVColor; //节点颜色
typedef enum {GETREE, GEBACK, GEFRONT, GEACCORSS}GEType; //边类型
typedef vector<int>::iterator GVit; //邻接节点迭代器
typedef vector<vector<int>> Glv; //邻接链表数组
typedef vector<vector<bool>> Gmtx; //邻接矩阵
typedef array<int, 2> GEdge; //边
typedef vector<vector<double>> Awfm; //权重、容量/流矩阵

class Graph {
public:
    static double constexpr MaxWeight = 1.0e128; //边或路径的权重最大极限
    bool is_dird; //是否为有向图
    bool is_cld; //是否有环
    vector<int> bdmpre; //记录bfs/dfs/msp/mst算法中结点的前驱
    Awfm wcm; //边/最短路径的权重/容量
    Glv lv; //邻接链表数组
    Gmtx mtx; //邻接矩阵
    char fvc; //第一个结点的字符表示
    vector<double> mtpwv; 
        //msp到节点的最短路径的权重数组
        //mst从子树中最近的前驱到当前节点的权重数组 
    vector<int> bd; //bfs 到源节点边距
    vector<int> vcc; //dfs 节点所属前驱树id/连通分量分组
    vector<GEType> etv; //edge type vector
    vector<vector<int>> amspre; //所有节点对的最短路径前驱矩阵
    vector<int>tporder; //节点的拓补排序数组
    int dv; //树的直径的一个端点
    stack<int> vs; //dfs结点递归发现栈
    vector<int> low; //当前接点可到达结点的最小dt值
    Glv ddcc; //点双连通分量数组
    vector<GEdge> ev; //边vector, 用于链式前向星
    vector<int> head; //链式前向星中各点的第一条出边
    int ccc; //cc cnt
    Awfm fm;
private:
    vector<double> ef; //超额流
    Awfm cfm; //容量矩阵
    vector<int>h; //流结点高度
    int tpc;  //拓补排序倒序计数器
    int childs; //dfs根结点的子树个数
    int time; //dfs时间计数器
    vector<int> dt; //dfs discover time
    vector<int> ft; //dfs finish time
    vector<GVColor> vc; //dfs vertex color
    
public:
    Graph(bool is_dird=true) : is_dird(is_dird) {}
    bool lv_olp_hhz(void);
        //无向图欧拉路径/回路hierholzer算法
        //生成欧拉路径的点栈: vs
        //可以有多重边和自环边
        //t: O(V+E) ?!
    void lv2lfs(void); 
        //邻接链表转链式前向星(link front start)
        //t: O(V+E)
    int lv_cag_mlsp(void); 
        //计算连通无向无环图中最长的最短路径-->树的直径
        //返回直径的一个端点, 另一个端点赋值成员变量dv
    int lv_dag_simle_paths(int s, int d);
    void lv_tp_order(void); //生成有向无环图的拓补排序tporder, t: O(V+E)
    void lv2mtx(void); //邻接链表转邻接矩阵，t: theta(V**2)
    void mtx2lv(void); //邻接矩阵转邻接链表, t: theta(V**2)
    void lv_print(void);
    void mtx_print(void);
    bool mtx_has_usink(void);
    bool mtx_has_usink0(void);
    Gmtx mtx_square(void);
    Glv lv_square(void);
    void lv_mflow_r2f(int s, int t);
        //有相图最大流前置重贴算法(Relabel2Front)
    void lv_mflow_pr_init(int s); //推送重贴算法初始化
    void lv_mflow_ffek(int s, int t);
        //有向图流网络最大流Ford-FulkERSON-Edmonds-Karp算法
        //@返回最大流的流矩阵
        //t: !!要求边容量为整数
    Awfm lv_amsp_johnson(void);
        //有向图的所有节点对的最短路径的johnson算法
        //@return: 节点对最短路径权重矩阵
        //t: O(VE+V*(V+E)lg(V)) = O(VE
    Awfm lv_amsp(void); 
        //无负权重环有向图的所有节点对的最短路径权重算法。
        //@return: 节点对最短路径权重矩阵
        //t: O(V^3*lgV)
    Awfm lv_amsp_fw(void); 
        //无负权重环有向图的所有节点对的最短路径的FLOYD-WARSHALL算法
        //运行过程中会构建前驱矩阵amspre, 可利用该矩阵输出任意节点对最短路径
        //@return: 节点对最短路径权重矩阵
        //t: O(V^3)
    bool lv_msp_bf(int s); 
        //有向图单源最短路径Bellman-Ford算法
        //@return: 如果包含s可到达的负权重环，则返回false
        //执行过程会生成终点前驱向量bdmpre, 最短路径权重mtpwv
        //t: theta(VE)
    void lv_mssp_bfl(int s);  //most shortest simple path
        //有向图单源最短简单路径Bellman-Ford算法
        //@return: 如果包含s可到达的负权重环，则返回false
        //执行过程会生成终点前驱向量bdmpre, 最短路径权重mtpwv
        //t: theta(V**2*E)
    void lv_msp_dijkstra(int s);
        //无负权重边有向图的单源最短路径dijkstra算法
        //t: O((V+E)*lgV)
    Glv lv_mst_kruskal(void); 
        //连通无向图的最小生成树的kruskal算法
        //@return: 生成树的邻接链表(双向邻接)
        //如果源图不连通，则返回的是所有连通分量对应生成树的森林的邻接链表
        //t: O(E*lg(V)) !!
    void lv_mst_prim(int s);
        //连通无向图的最小生成树的prim算法
        //s: 将要构建的的最小生成树的根
        //运行过程中会构建前驱数组bdmpre, 其对应的前驱图的边和最小生成树的一一对
        //应。
        //如果源图不连通，则返回的是所有连通分量对应生成树的森林的邻接链表
        //t: O(E*lg(V)) !!
    Glv lv_trans(void); //返回源图的转置的邻接链表, t: O(V+E)
    Gmtx mtx_trans(void); //返回源图的转置的邻接矩阵, t: O(V**2)
    void lv_trim(void); //裁剪有向图中自循边和冗余边, t: O(V+E)
    void lv_bfs(int s); //源图已节点s为根的广度优先搜索, t: O(V+E)
    void lv_dfs(void); 
        //图的深度优先搜索
        //会构建前驱森林对应的前驱数组bdmpre, 拓补排序数组tporder, 边类型矩阵et
        //t: theta(V^2), 由于要记录边类形导致复杂度上界从V+E增大至V^2
    void lv_dfs_noet(void); 
        //无边类型dfs
        //t: theta(V+E)
    void lv_dfs_nor(void); 
        //去递归版dfs
        //t: theta(V^2), 由于要记录边类形导致复杂度上界从V+E增大至V^2
    void lv_dfs_nor_noet(void); 
        //非递归无边类型dfs
        //t: theta(O+E)
    vector<int> lv_strong_con_compts(void);
        //有向图的强连通分量算法
        //@return: 各节点对应的强连通分量id
        //t: theta(V+E)
    void lv_tarjan_edcc(void);
    void lv_tarjan_edcc_core(int i);
    void lv_tarjan_ddcc(void);
    void lv_tarjan_ddcc_core(int i);
    void lv_tarjan_bridge(void);
    void lv_tarjan_bridge_core(int i);
    void lv_tarjan_cdot(void);
    void lv_tarjan_cdot_core(int i);
    void lv_tarjan_scc(void);
    void lv_tarjan_scc_core(int i);
    void lv_dag_msp(int s); 
        //DAG: directed acyclic graph 有向无环图单源最短路径算法
        //t: theta(V+E)
    bool lv_spath_print(int s, int d); 
        //打印bfs/dfs/msp前驱搜索路径
        //@return: 如果路径不存在返回false
        //t: O(V)
    bool lv_spath_printc(int s, int d);
        //以字母形式打印路径
private:
    void lv_olp_hhz_core(int s);
        //欧拉路径hhz算法核心
        //t: O(E), 采用摊还分析(除根调用，其他递归调用都只对应一条边)
    void add_edge(int u, int v); //链式前向星加边
    void lv_mflow_pr_push(int u, int v);
    void lv_mflow_pr_relabel(int u);
    
    bool lv_has_same_branch(int u, int v);
        //最短简单路径算法中判断v是否已在u的分支上，防止成环
    void lv_amsp_init(Awfm &m); 
        //所有节点对最短路径权重矩阵初始化
    void lv_amsp_eadd(Awfm &m1, Awfm &m2);
        //所有节点对的最短路径的算法的权重矩阵的最大边数的倍增函数
        //t: O(V**3))
    void lv_dfs_init(void); //dfs初始化， t: theta(V**2)
    void lv_dfs_noet_init(void); //dfs无边类型初始化， t: theta(V+E)
    void lv_dfs_visit(int u);
        //dfs中发现新节点后的递归处理步骤, t: O(V)
    void lv_dfs_noet_visit(int u);
        //无边类型dfs中发现新节点后的递归处理步骤
    void lv_dfs_deal_vgb(int u, int j); 
        //dfs中用于处理发现灰色和黑色节点时对应的边类型
    void lv_dfs_nor_with_order(vector<int> &ord); 
        //指定节点遍历顺序的非递归dfs
        //t: theta(V**2)
    void lv_dfs_nor_noet_with_order(vector<int> &ord); 
        //指定节点遍历顺序的非递归无边类型dfs
        //t: O(V+E)
    void lv_dfs_nor_lpcore(stack<int> &es); 
        //非递归dfs中发现新节点后的循环处理步骤, t: O(V+E)
    void lv_dfs_nor_noet_lpcore(stack<GVit> &its);
        //非递归无边类型dfs中发现新节点后的循环处理步骤, t: O(V+E)
    void lv_msp_relax(int u, int v);
        //msp算法的节点松弛步骤, t: theta(1)
    void lv_msp_init(int s);
        //msp算法初始化步骤, O(V)
};

#endif //GRAPH_H
